
// Copyright (c) 2018 brinkqiang (brink.qiang@gmail.com)
//
// Permission is hereby granted, free of charge, to any person obtaining a copy
// of this software and associated documentation files (the "Software"), to deal
// in the Software without restriction, including without limitation the rights
// to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
// copies of the Software, and to permit persons to whom the Software is
// furnished to do so, subject to the following conditions:
//
// The above copyright notice and this permission notice shall be included in all
// copies or substantial portions of the Software.
//
// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
// OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
// SOFTWARE.

#ifndef _LIST_H_INCLUDE_
#define _LIST_H_INCLUDE_

#include <stddef.h>

/*
 * Simple doubly linked list implementation.
 *
 * Some of the internal functions ("__xxx") are useful when
 * manipulating whole lists rather than single entries, as
 * sometimes we already know the next/prev entries and we can
 * generate better code by using them directly rather than
 * using the generic single-entry routines.
 */
#define LIST_POISON1 ((void *) 0x00100100)
#define LIST_POISON2 ((void *) 0x00200200)

#ifndef NULL
#define NULL 0
#endif

#ifndef container_of
#define container_of(ptr, type, member)  ((type*)((char*)ptr - offsetof(type, member)))
#endif

struct list_head {
    struct list_head* next, *prev;
};

#define LIST_HEAD_INIT(name) { &(name), &(name) }

#define LIST_HEAD(name) \
    struct list_head name = LIST_HEAD_INIT(name)

static inline void INIT_LIST_HEAD( struct list_head* list ) {
    list->next = list;
    list->prev = list;
}

/*
 * Insert a newone entry between two known consecutive entries.
 *
 * This is only for internal list manipulation where we know
 * the prev/next entries already!
 */
#ifndef CONFIG_DEBUG_LIST
static inline void __list_add( struct list_head* newone, struct list_head* prev, struct list_head* next ) {
    next->prev = newone;
    newone->next = next;
    newone->prev = prev;
    prev->next = newone;
}
#else
extern void __list_add( struct list_head* newone, struct list_head* prev, struct list_head* next );
#endif

/**
 * list_add - add a newone entry
 * @newone: newone entry to be added
 * @head: list head to add it after
 *
 * Insert a newone entry after the specified head.
 * This is good for implementing stacks.
 */
static inline void list_add( struct list_head* newone, struct list_head* head ) {
    __list_add( newone, head, head->next );
}


/**
 * list_add_tail - add a newone entry
 * @newone: newone entry to be added
 * @head: list head to add it before
 *
 * Insert a newone entry before the specified head.
 * This is useful for implementing queues.
 */
static inline void list_add_tail( struct list_head* newone, struct list_head* head ) {
    __list_add( newone, head->prev, head );
}

/*
 * list_add_tail - add a newone entry
 * @newone: newone entry to be added
 * @head: list head to add it before
 *
 * Insert a newone entry before the specified head.
 * This is useful for implementing queues.
 */
static inline void list_add_front(struct list_head* newone, struct list_head* head) {
	__list_add(newone, head, head->next);
}

/*
 * Delete a list entry by making the prev/next entries
 * point to each other.
 *
 * This is only for internal list manipulation where we know
 * the prev/next entries already!
 */
static inline void __list_del( struct list_head* prev, struct list_head* next ) {
    next->prev = prev;
    prev->next = next;
}

/**
 * list_del - deletes entry from list.
 * @entry: the element to delete from the list.
 * Note: list_empty() on entry does not return true after this, the entry is
 * in an undefined state.
 */
#ifndef CONFIG_DEBUG_LIST
static inline void list_del( struct list_head* entry ) {
    __list_del( entry->prev, entry->next );
    entry->next = ( struct list_head* )LIST_POISON1;
    entry->prev = ( struct list_head* )LIST_POISON2;
}
#else
extern void list_del( struct list_head* entry );
#endif

/**
 * list_replace - replace old entry by newone one
 * @old : the element to be replaced
 * @newone : the newone element to insert
 *
 * If @old was empty, it will be overwritten.
 */
static inline void list_replace( struct list_head* old, struct list_head* newone ) {
    newone->next = old->next;
    newone->next->prev = newone;
    newone->prev = old->prev;
    newone->prev->next = newone;
}

static inline void list_replace_init( struct list_head* old, struct list_head* newone ) {
    list_replace( old, newone );
    INIT_LIST_HEAD( old );
}

/**
 * list_del_init - deletes entry from list and reinitialize it.
 * @entry: the element to delete from the list.
 */
static inline void list_del_init( struct list_head* entry ) {
    __list_del( entry->prev, entry->next );
    INIT_LIST_HEAD( entry );
}

/**
 * list_move - delete from one list and add as another's head
 * @list: the entry to move
 * @head: the head that will precede our entry
 */
static inline void list_move( struct list_head* list, struct list_head* head ) {
    __list_del( list->prev, list->next );
    list_add( list, head );
}

/**
 * list_move_tail - delete from one list and add as another's tail
 * @list: the entry to move
 * @head: the head that will follow our entry
 */
static inline void list_move_tail( struct list_head* list, struct list_head* head ) {
    __list_del( list->prev, list->next );
    list_add_tail( list, head );
}

/**
 * list_is_last - tests whether @list is the last entry in list @head
 * @list: the entry to test
 * @head: the head of the list
 */
static inline int list_is_last( const struct list_head* list, const struct list_head* head ) {
    return list->next == head;
}

/**
 * list_empty - tests whether a list is empty
 * @head: the list to test.
 */
static inline int list_empty( const struct list_head* head ) {
    return head->next == head;
}

/**
 * list_empty_careful - tests whether a list is empty and not being modified
 * @head: the list to test
 *
 * Description:
 * tests whether a list is empty _and_ checks that no other CPU might be
 * in the process of modifying either member (next or prev)
 *
 * NOTE: using list_empty_careful() without synchronization
 * can only be safe if the only activity that can happen
 * to the list entry is list_del_init(). Eg. it cannot be used
 * if another CPU could re-list_add() it.
 */
static inline int list_empty_careful( const struct list_head* head ) {
    struct list_head* next = head->next;
    return ( next == head ) && ( next == head->prev );
}

/**
 * list_is_singular - tests whether a list has just one entry.
 * @head: the list to test.
 */
static inline int list_is_singular( const struct list_head* head ) {
    return !list_empty( head ) && ( head->next == head->prev );
}

static inline void __list_cut_position( struct list_head* list, struct list_head* head, struct list_head* entry ) {
    struct list_head* new_first = entry->next;
    list->next = head->next;
    list->next->prev = list;
    list->prev = entry;
    entry->next = list;
    head->next = new_first;
    new_first->prev = head;
}

/**
 * list_cut_position - cut a list into two
 * @list: a newone list to add all removed entries
 * @head: a list with entries
 * @entry: an entry within head, could be the head itself
 *      and if so we won't cut the list
 *
 * This helper moves the initial part of @head, up to and
 * including @entry, from @head to @list. You should
 * pass on @entry an element you know is on @head. @list
 * should be an empty list or a list you do not care about
 * losing its data.
 *
 */
static inline void list_cut_position( struct list_head* list, struct list_head* head, struct list_head* entry ) {
    if ( list_empty( head ) ) {
        return;
    }

    if ( list_is_singular( head ) && ( head->next != entry && head != entry ) ) {
        return;
    }

    if ( entry == head ) {
        INIT_LIST_HEAD( list );
    }
    else {
        __list_cut_position( list, head, entry );
    }
}

static inline void __list_splice( const struct list_head* list, struct list_head* prev, struct list_head* next ) {
    struct list_head* first = list->next;
    struct list_head* last = list->prev;
    first->prev = prev;
    prev->next = first;
    last->next = next;
    next->prev = last;
}

/**
 * list_splice - join two lists, this is designed for stacks
 * @list: the newone list to add.
 * @head: the place to add it in the first list.
 */
static inline void list_splice( const struct list_head* list, struct list_head* head ) {
    if ( !list_empty( list ) ) {
        __list_splice( list, head, head->next );
    }
}

/**
 * list_splice_tail - join two lists, each list being a queue
 * @list: the newone list to add.
 * @head: the place to add it in the first list.
 */
static inline void list_splice_tail( struct list_head* list, struct list_head* head ) {
    if ( !list_empty( list ) ) {
        __list_splice( list, head->prev, head );
    }
}

/**
 * list_splice_init - join two lists and reinitialise the emptied list.
 * @list: the newone list to add.
 * @head: the place to add it in the first list.
 *
 * The list at @list is reinitialised
 */
static inline void list_splice_init( struct list_head* list, struct list_head* head ) {
    if ( !list_empty( list ) ) {
        __list_splice( list, head, head->next );
        INIT_LIST_HEAD( list );
    }
}

/**
 * list_splice_tail_init - join two lists and reinitialise the emptied list
 * @list: the newone list to add.
 * @head: the place to add it in the first list.
 *
 * Each of the lists is a queue.
 * The list at @list is reinitialised
 */
static inline void list_splice_tail_init( struct list_head* list, struct list_head* head ) {
    if ( !list_empty( list ) ) {
        __list_splice( list, head->prev, head );
        INIT_LIST_HEAD( list );
    }
}

/**
 * list_entry - get the struct for this entry
 * @ptr:        the &struct list_head pointer.
 * @type:       the type of the struct this is embedded in.
 * @member:     the name of the list_struct within the struct.
 */
#define list_entry(ptr, type, member) \
    container_of(ptr, type, member)

/**
 * list_first_entry - get the first element from a list
 * @ptr:        the list head to take the element from.
 * @type:       the type of the struct this is embedded in.
 * @member:     the name of the list_struct within the struct.
 *
 * Note, that list is expected to be not empty.
 */
#define list_first_entry(ptr, type, member) \
    list_entry((ptr)->next, type, member)

/**
 * list_for_each        -       iterate over a list
 * @pos:        the &struct list_head to use as a loop cursor.
 * @head:       the head for your list.
 */
#define list_for_each(pos, head) \
    for (pos = (head)->next; prefetch(pos->next), pos != (head); pos = pos->next)

/**
 * __list_for_each      -       iterate over a list
 * @pos:        the &struct list_head to use as a loop cursor.
 * @head:       the head for your list.
 *
 * This variant differs from list_for_each() in that it's the
 * simplest possible list iteration code, no prefetching is done.
 * Use this for code that knows the list to be very short (empty
 * or 1 entry) most of the time.
 */
#define __list_for_each(pos, head) \
    for (pos = (head)->next; pos != (head); pos = pos->next)

/**
 * list_for_each_prev   -       iterate over a list backwards
 * @pos:        the &struct list_head to use as a loop cursor.
 * @head:       the head for your list.
 */
#define list_for_each_prev(pos, head) \
    for (pos = (head)->prev; prefetch(pos->prev), pos != (head); pos = pos->prev)

/**
 * list_for_each_safe - iterate over a list safe against removal of list entry
 * @pos:        the &struct list_head to use as a loop cursor.
 * @n:          another &struct list_head to use as temporary storage
 * @head:       the head for your list.
 */
#define list_for_each_safe(pos, n, head) \
    for (pos = (head)->next, n = pos->next; pos != (head); pos = n, n = pos->next)

/**
 * list_for_each_prev_safe - iterate over a list backwards safe against removal of list entry
 * @pos:        the &struct list_head to use as a loop cursor.
 * @n:          another &struct list_head to use as temporary storage
 * @head:       the head for your list.
 */
#define list_for_each_prev_safe(pos, n, head) \
    for (pos = (head)->prev, n = pos->prev; prefetch(pos->prev), pos != (head); pos = n, n = pos->prev)

/**
 * list_for_each_entry  -       iterate over list of given type
 * @pos:        the type * to use as a loop cursor.
 * @head:       the head for your list.
 * @member:     the name of the list_struct within the struct.
 */
#define list_for_each_entry(pos, head, member)                           \
    for (pos = list_entry((head)->next, typeof(*pos), member);           \
                prefetch(pos->member.next), &pos->member != (head);      \
                pos = list_entry(pos->member.next, typeof(*pos), member))

/**
 * list_for_each_entry_reverse - iterate backwards over list of given type.
 * @pos:        the type * to use as a loop cursor.
 * @head:       the head for your list.
 * @member:     the name of the list_struct within the struct.
 */
#define list_for_each_entry_reverse(pos, head, member)                  \
    for (pos = list_entry((head)->prev, typeof(*pos), member);          \
                prefetch(pos->member.prev), &pos->member != (head);     \
                pos = list_entry(pos->member.prev, typeof(*pos), member))

/**
 * list_prepare_entry - prepare a pos entry for use in list_for_each_entry_continue()
 * @pos:        the type * to use as a start point
 * @head:       the head of the list
 * @member:     the name of the list_struct within the struct.
 *
 * Prepares a pos entry for use as a start point in list_for_each_entry_continue().
 */
#define list_prepare_entry(pos, head, member) \
    ((pos) ? : list_entry(head, typeof(*pos), member))

/**
 * list_for_each_entry_continue - continue iteration over list of given type
 * @pos:        the type * to use as a loop cursor.
 * @head:       the head for your list.
 * @member:     the name of the list_struct within the struct.
 *
 * Continue to iterate over list of given type, continuing after
 * the current position.
 */
#define list_for_each_entry_continue(pos, head, member)                 \
    for (pos = list_entry(pos->member.next, typeof(*pos), member);      \
                prefetch(pos->member.next), &pos->member != (head);     \
                pos = list_entry(pos->member.next, typeof(*pos), member))

/**
 * list_for_each_entry_continue_reverse - iterate backwards from the given point
 * @pos:        the type * to use as a loop cursor.
 * @head:       the head for your list.
 * @member:     the name of the list_struct within the struct.
 *
 * Start to iterate over list of given type backwards, continuing after
 * the current position.
 */
#define list_for_each_entry_continue_reverse(pos, head, member)         \
    for (pos = list_entry(pos->member.prev, typeof(*pos), member);      \
                prefetch(pos->member.prev), &pos->member != (head);     \
                pos = list_entry(pos->member.prev, typeof(*pos), member))

/**
 * list_for_each_entry_from - iterate over list of given type from the current point
 * @pos:        the type * to use as a loop cursor.
 * @head:       the head for your list.
 * @member:     the name of the list_struct within the struct.
 *
 * Iterate over list of given type, continuing from current position.
 */
#define list_for_each_entry_from(pos, head, member)             \
    for (; prefetch(pos->member.next), &pos->member != (head);  \
                pos = list_entry(pos->member.next, typeof(*pos), member))

/**
 * list_for_each_entry_safe - iterate over list of given type safe against removal of list entry
 * @pos:        the type * to use as a loop cursor.
 * @n:          another type * to use as temporary storage
 * @head:       the head for your list.
 * @member:     the name of the list_struct within the struct.
 */
#define list_for_each_entry_safe(pos, n, head, member)                  \
    for (pos = list_entry((head)->next, typeof(*pos), member),          \
                n = list_entry(pos->member.next, typeof(*pos), member); \
                &pos->member != (head);                                 \
                pos = n, n = list_entry(n->member.next, typeof(*n), member))

/**
 * list_for_each_entry_safe_continue
 * @pos:        the type * to use as a loop cursor.
 * @n:          another type * to use as temporary storage
 * @head:       the head for your list.
 * @member:     the name of the list_struct within the struct.
 *
 * Iterate over list of given type, continuing after current point,
 * safe against removal of list entry.
 */
#define list_for_each_entry_safe_continue(pos, n, head, member)                 \
    for (pos = list_entry(pos->member.next, typeof(*pos), member),              \
                n = list_entry(pos->member.next, typeof(*pos), member);         \
                &pos->member != (head);                                         \
                pos = n, n = list_entry(n->member.next, typeof(*n), member))

/**
 * list_for_each_entry_safe_from
 * @pos:        the type * to use as a loop cursor.
 * @n:          another type * to use as temporary storage
 * @head:       the head for your list.
 * @member:     the name of the list_struct within the struct.
 *
 * Iterate over list of given type from current point, safe against
 * removal of list entry.
 */
#define list_for_each_entry_safe_from(pos, n, head, member)                     \
    for (n = list_entry(pos->member.next, typeof(*pos), member);                \
                &pos->member != (head);                                         \
                pos = n, n = list_entry(n->member.next, typeof(*n), member))

/**
 * list_for_each_entry_safe_reverse
 * @pos:        the type * to use as a loop cursor.
 * @n:          another type * to use as temporary storage
 * @head:       the head for your list.
 * @member:     the name of the list_struct within the struct.
 *
 * Iterate backwards over list of given type, safe against removal
 * of list entry.
 */
#define list_for_each_entry_safe_reverse(pos, n, head, member)          \
    for (pos = list_entry((head)->prev, typeof(*pos), member),          \
                n = list_entry(pos->member.prev, typeof(*pos), member); \
                &pos->member != (head);                                 \
                pos = n, n = list_entry(n->member.prev, typeof(*n), member))

/*
 * Double linked lists with a single pointer list head.
 * Mostly useful for hash tables where the two pointer list head is
 * too wasteful.
 * You lose the ability to access the tail in O(1).
 */

struct hlist_head {
    struct hlist_node* first;
};

struct hlist_node {
    struct hlist_node* next, ** pprev;
};

#define HLIST_HEAD_INIT { .first = NULL }
#define HLIST_HEAD(name) struct hlist_head name = {  .first = NULL }
#define INIT_HLIST_HEAD(ptr) ((ptr)->first = NULL)
static inline void INIT_HLIST_NODE( struct hlist_node* h ) {
    h->next = NULL;
    h->pprev = NULL;
}

static inline int hlist_unhashed( const struct hlist_node* h ) {
    return !h->pprev;
}

static inline int hlist_empty( const struct hlist_head* h ) {
    return !h->first;
}

static inline void __hlist_del( struct hlist_node* n ) {
    struct hlist_node* next = n->next;
    struct hlist_node** pprev = n->pprev;
    *pprev = next;

    if ( next ) {
        next->pprev = pprev;
    }
}

static inline void hlist_del( struct hlist_node* n ) {
    __hlist_del( n );
    n->next = ( struct hlist_node* )LIST_POISON1;
    n->pprev = ( struct hlist_node** )LIST_POISON2;
}

static inline void hlist_del_init( struct hlist_node* n ) {
    if ( !hlist_unhashed( n ) ) {
        __hlist_del( n );
        INIT_HLIST_NODE( n );
    }
}

static inline void hlist_add_head( struct hlist_node* n,
                                   struct hlist_head* h ) {
    struct hlist_node* first = h->first;
    n->next = first;

    if ( first ) {
        first->pprev = &n->next;
    }

    h->first = n;
    n->pprev = &h->first;
}

/* next must be != NULL */
static inline void hlist_add_before( struct hlist_node* n,
                                     struct hlist_node* next ) {
    n->pprev = next->pprev;
    n->next = next;
    next->pprev = &n->next;
    *( n->pprev ) = n;
}

static inline void hlist_add_after( struct hlist_node* n,
                                    struct hlist_node* next ) {
    next->next = n->next;
    n->next = next;
    next->pprev = &n->next;

    if ( next->next ) {
        next->next->pprev  = &next->next;
    }
}

/*
 * Move a list from one list head to another. Fixup the pprev
 * reference of the first entry if it exists.
 */
static inline void hlist_move_list( struct hlist_head* old,
                                    struct hlist_head* newone ) {
    newone->first = old->first;

    if ( newone->first ) {
        newone->first->pprev = &newone->first;
    }

    old->first = NULL;
}

#define hlist_entry(ptr, type, member) container_of(ptr,type,member)

#define hlist_for_each(pos, head) \
    for (pos = (head)->first; pos && ({ prefetch(pos->next); 1; }); \
                pos = pos->next)

#define hlist_for_each_safe(pos, n, head) \
    for (pos = (head)->first; pos && ({ n = pos->next; 1; }); \
                pos = n)

/**
 * hlist_for_each_entry - iterate over list of given type
 * @tpos:       the type * to use as a loop cursor.
 * @pos:        the &struct hlist_node to use as a loop cursor.
 * @head:       the head for your list.
 * @member:     the name of the hlist_node within the struct.
 */
#define hlist_for_each_entry(tpos, pos, head, member)                    \
    for (pos = (head)->first;                                    \
                pos && ({ prefetch(pos->next); 1;}) &&                       \
                ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
                pos = pos->next)

/**
 * hlist_for_each_entry_continue - iterate over a hlist continuing after current point
 * @tpos:       the type * to use as a loop cursor.
 * @pos:        the &struct hlist_node to use as a loop cursor.
 * @member:     the name of the hlist_node within the struct.
 */
#define hlist_for_each_entry_continue(tpos, pos, member)                 \
    for (pos = (pos)->next;                                              \
                pos && ({ prefetch(pos->next); 1;}) &&                       \
                ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
                pos = pos->next)

/**
 * hlist_for_each_entry_from - iterate over a hlist continuing from current point
 * @tpos:       the type * to use as a loop cursor.
 * @pos:        the &struct hlist_node to use as a loop cursor.
 * @member:     the name of the hlist_node within the struct.
 */
#define hlist_for_each_entry_from(tpos, pos, member)                     \
    for (; pos && ({ prefetch(pos->next); 1;}) &&                        \
                ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
                pos = pos->next)

/**
 * hlist_for_each_entry_safe - iterate over list of given type safe against removal of list entry
 * @tpos:       the type * to use as a loop cursor.
 * @pos:        the &struct hlist_node to use as a loop cursor.
 * @n:          another &struct hlist_node to use as temporary storage
 * @head:       the head for your list.
 * @member:     the name of the hlist_node within the struct.
 */
#define hlist_for_each_entry_safe(tpos, pos, n, head, member)            \
    for (pos = (head)->first;                                    \
                pos && ({ n = pos->next; 1; }) &&                            \
                ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
                pos = n)

#endif // __DMLIST_H_INCLUDE__

